public class Tester {
	
	
	public static void main(String[] args) {
		if (!emptyTreeTest()){
			System.out.println("ERROR: emptyTreeTest");
		}
		if (!searchTest()){
			System.out.println("ERROR: searchTest");
		}
		if (!inseartTest()){
			System.out.println("ERROR: inseartTest");
		}
		if (!deleteTest()){
			System.out.println("ERROR: deleteTest");
		}
		if (!successorTest()){
			System.out.println("ERROR: successorTest");
		}
		if (!predecessorTest()){
			System.out.println("ERROR: predecessorTest");
		}
		if (!depthTest()){
			System.out.println("ERROR: depthTest");
		}	
		System.out.println("END TESTS");
	}

	

	private static boolean emptyTreeTest(){
		RBTree t = new RBTree();
		if (!t.empty()){
			return false;
		}
		t.insert(1, "empty test");
		if(t.empty()){
			return false;
		}
		t.delete(1);
		if (!t.empty()){
			return false;
		}
		return true;
	}
	
	private static boolean searchTest(){
		RBTree t = new RBTree();
		if(t.search(1) != null){
			return false;
		}
		int numOfNodes = 10000;
		for (int i = 0; i < numOfNodes; i++) {
			t.insert(i, String.valueOf(i+10));
		}
		for (int i = 0; i < numOfNodes; i++){
			if(!String.valueOf(i+10).equals(t.search(i))){
				return false;
			}
		}
		for (int i = 0; i < numOfNodes; i++){
			if (i%2 == 0){
				t.delete(i);
			}
		}
		for (int i = 0; i < numOfNodes; i++){
			if (i%2 == 0){
				if(t.search(i) != null){
					return false;
				}
			}
			else{
				if(!String.valueOf(i+10).equals(t.search(i))){
					return false;
				}
			}
		}
		return true;
	}
	
	private static boolean inseartTest(){
		RBTree t = new RBTree();
		for (int i = 0; i < 100; i++) {
			t.insert(i, String.valueOf(i+10));
			if ((true!= t.isValid()) || (!String.valueOf(i+10).equals(t.search(i))) || (i+1 !=  t.size())){
				return false;
			}
		}
		int size = 100;
		for (int i = 300; i > 200; i--) {
			t.insert(i, String.valueOf(i+10));
			if ((true != t.isValid()) || (!String.valueOf(i+10).equals(t.search(i))) || (++size != t.size())){
				return false;
			}
		}
		for (int i = 100; i < 200; i++) {
			t.insert(i, String.valueOf(i+10));
			if((true != t.isValid()) || (!String.valueOf(i+10).equals(t.search(i))) || (++size != t.size())){
				return false;
			}
		}
		return true;
	}

	private static boolean deleteTest(){
		RBTree t = new RBTree();
		for (int i = 0; i < 300; i++) {
			t.insert(i, String.valueOf(i+10));
			if((true != t.isValid()) || (!String.valueOf(i+10).equals(t.search(i))) || (i+1 != t.size())){
				return false;
			}
		}
		int size = 300;
		for (int i = 100; i < 200; i++) {
			t.delete(i);
			if ((t.isValid() != true) || (t.search(i) != null) || (--size != t.size())){
				return false;
			}
		}
		for (int i = 250; i < 300; i++) {
			t.delete(i);
			if ((t.isValid() != true) || (t.search(i) != null) || (--size != t.size())){
				return false;
			}
		}
		for (int i = 0; i < 50; i++) {
			t.delete(i);
			if ((true != t.isValid()) || (null != t.search(i)) || (--size != t.size())){
				return false;
			}
		}
		for (int i = 99; i > 49; i--) {
			t.delete(i);
			if ((true != t.isValid()) || (null != t.search(i)) || (--size != t.size())){
				return false;
			}
		}
		for (int i = 249; i > 199; i--) {
			t.delete(i);
			if ((true != t.isValid()) || (null != t.search(i)) || (--size != t.size())){
				return false;
			}
		}
		if (true != t.empty()){
			return false;
		}
		return true;
	}

	private static boolean successorTest(){
		RBTree t = new RBTree();
		for (int i = 0; i < 1000; i++) {
			t.insert(i, String.valueOf(i+10));
		}
		for (int i = 0; i < 999; i++) {
			if (i+1 !=t.successor(i)){
				return false;
			}
		}
		//if (Integer.MIN_VALUE != t.successor(5000)){
		//	return false;
		//}
		t.delete(7);
		//if (Integer.MIN_VALUE != t.successor(7)){
		//	return false;
		//}
		//if(Integer.MAX_VALUE != t.successor(999)){
		//	return false;
		//}
		return true;
	}
	
	private static boolean predecessorTest(){
		RBTree t = new RBTree();
		for (int i = 0; i < 1000; i++) {
			t.insert(i, String.valueOf(i+10));
		}
		//if (Integer.MAX_VALUE != t.predecessor(0)){
		//	return false;
		//}
		for (int i = 1; i < 1000; i++) {
			if (i-1 != t.predecessor(i)){
				return false;
			}
		}
		//if (Integer.MIN_VALUE != t.predecessor(5000)){
		//	return false;
		//}
		t.delete(7);
		//if (Integer.MIN_VALUE != t.successor(7)){
		//	return false;
		//}
		return true;
	}
	
	private static boolean depthTest(){
		RBTree t = new RBTree();
		for (int i = 0; i < 1000000; i++) {
			t.insert(i, String.valueOf(i+10));
		}
		if ((t.maxDepth() < 20) || (t.maxDepth() > 40)){
			return false;
		}
		return true;
	}
	
}
